#include <bits/stdc++.h>

#define eb emplace_back
#define ep emplace
#define fi first
#define se second
#define in read<int>()
#define lin read<ll>()
#define rep(i, x, y) for(int i = (x); i <= (y); i++)
#define per(i, x, y) for(int i = (x); i >= (y); i--)

using namespace std;

using ll = long long;
using db = double;
using pii = pair < int, int >;
using vec = vector < int >;
using veg = vector < pii >;

template < typename T > T read() {
	T x = 0; bool f = 0; char ch = getchar();
	while(!isdigit(ch)) f |= ch == '-', ch = getchar();
	while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
	return f ? -x : x;
}

template < typename T > void chkmax(T &x, const T &y) { x = x > y ? x : y; }
template < typename T > void chkmin(T &x, const T &y) { x = x < y ? x : y; }

const int N = 1e6 + 10;

int n, siz[N];
vec G[N];
ll ans1, ans2;

namespace calcmn {
	bool fl[N];
	int p[N];
	void dfs(int x, int p) {
		fl[x] = true; calcmn :: p[x] = x;
		for(auto y : G[x]) if(y ^ p) {
				dfs(y, x);
				if(fl[y]) swap(calcmn :: p[x], calcmn :: p[y]), fl[y] = fl[x] = false, ans1 += 2;
			}
	}
	void solve() { dfs(1, 0); if(fl[1]) for(auto y : G[1]) { swap(p[1], p[y]), fl[1] = fl[y] = false, ans1 += 2; break; } }
	void out() { rep(i, 1, n) printf("%d ", p[i]); puts(""); }
}

namespace calcmx {
	int p[N], siz[N], son[N];
	bool vis[N];
	vec vpot[N];
	void dfs(int x, int p) {
		siz[x] = 1; for(auto y : G[x]) if(y ^ p) dfs(y, x), siz[x] += siz[y];
		ans2 += min(siz[x], n - siz[x]) * 2;
	}
	void gsz(int x, int p) {
		son[x] = 0; siz[x] = 1; for(auto y : G[x]) if(!vis[y] && y ^ p) gsz(y, x), siz[x] += siz[y], chkmax(son[x], siz[y]);
	}
	int rt;
	void grt(int x, int p, int tsz) {
		chkmax(son[x], tsz - siz[x]); for(auto y : G[x]) if(!vis[y] && y ^ p) grt(y, x, tsz);
		if(rt == 0 || son[x] < son[rt]) rt = x;
	}
	void tdfs(int x, int p, int bel) {
		vpot[bel].eb(x);
		for(auto y : G[x]) if(y ^ p && !vis[y]) tdfs(y, x, bel);
	}
	void divide(int x) {
		gsz(x, 0); rt = 0; grt(x, 0, siz[x]); x = rt; vis[x] = true;
		for(auto y : G[x]) if(!vis[y]) vpot[y].clear(), tdfs(y, x, y);
		sort(G[x].begin(), G[x].end(), [](auto a, auto b) { return vpot[a].size() > vpot[b].size(); });
		vec curpot(1, x);
		for(auto y : G[x]) if(!vis[y]) {
				vec tpot = vpot[y];
				while(curpot.size() && tpot.size()) {
					swap(p[curpot.back()], p[tpot.back()]);
					curpot.pop_back(); tpot.pop_back();
				} if(!curpot.size()) curpot = tpot;
			}
		//cerr << curpot.size() << endl;
		for(auto y : G[x]) if(!vis[y]) {
				vec tpot = vpot[y];
				while(curpot.size() && tpot.size()) {
					swap(p[curpot.back()], p[tpot.back()]);
					curpot.pop_back(); tpot.pop_back();
				} if(!curpot.size()) break;
			}
		//cerr << curpot.size() << endl;
		return;
		//assert(!curpot.size());
		for(auto y : G[x]) if(!vis[y]) divide(y);
	}
	void solve() {
		dfs(1, 0); iota(p + 1, p + n + 1, 1); divide(1);
	}
	void out() { rep(i, 1, n) printf("%d ", p[i]); puts(""); }
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("1.in", "r", stdin); freopen("1.out", "w", stdout);
#endif
	n = in; rep(i, 1, n - 1) { int u = in, v = in; G[u].eb(v); G[v].eb(u); }
	calcmn :: solve(); calcmx :: solve();
	printf("%lld %lld\n", ans1, ans2);
	calcmn :: out(); calcmx :: out();
	return 0;
}
